package com.wtgroup.demo.mianshi.算法.二叉树.model;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

/**
 * @author L&J
 * @version 0.0.0
 * @email liuhejun108@163.com
 * @date 2019/9/7 23:21
 */
public class CompleteBinTree<T> {
    // private Node<T>       root;
    /**
     * 按照广度优先的顺序存储, 即自上而下, 自左至右的顺序.
     * 每次追加时根据情况, 更新下次追加节点时的父节点.
     * 这里面的顺序直接就是 BFS 的顺序
     */
    private List<Node<T>> nodes  = new ArrayList<Node<T>>();
    /**
     * 当前节点追加了右节点后, 触发更新 offset , 即下次追加节点时, 目标父节点时 nodes[offset] .
     */
    private int           offset = 0;

    public CompleteBinTree() {
    }

    /**
     * 根据数据构建完全二叉树.
     * 逐层新增节点. 自上而下, 自左到右.
     *
     * @param datas
     */
    public CompleteBinTree( Collection<T> datas ) {
        if ( datas == null ) {
            throw new IllegalArgumentException();
        }
        if ( !datas.isEmpty() ) {
            for ( T data : datas ) {
                Node<T> tNode = new Node<T>(data);
                this.appendNode(tNode);
            }
        }
    }

    public CompleteBinTree<T> appendNode( Node<T> node ) {
        if ( node == null ) {
            return this;
        }
        if ( !isEmpty() ) {
            Node<T> curParent = nodes.get(offset);
            if ( curParent == null ) {
                curParent = node;
            } else if ( curParent.getLeft() == null ) {
                curParent.appendLeft(node);
            } else {
                curParent.appendRight(node);
                // 更新下次的目标父节点
                offset++;
            }
        }

        nodes.add(node);

        return this;
    }

    public Node<T> getRoot() {
        return nodes.size() == 0 ? null : nodes.get(0);
    }

    public boolean isEmpty() {
        return nodes.isEmpty();
    }

    @Override
    public String toString() {
        return nodes.toString();
    }
}
